package luo.hui.jiang.sort;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author 罗惠江
 * @version 1.0
 * @email 1511619294@qq.com
 * @date 2020/7/30 21:30
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[100000];

        for (int i = 0; i < 100000; i++) {
            arr[i] = (int) (Math.random() * 80000000);  //生成随机数组
        }
//                int arr[] = {3, 9, -1, 10, 20};
//        System.out.println(Arrays.toString(arr));
        long startTime = System.currentTimeMillis();
        insertSort(arr);
        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
//        System.out.println(Arrays.toString(arr));

    }

    /**
     * 插入排序思路：
     * 先将一边看做排序好的
     * 外层for 循环将 我们的数组进行遍历
     * 里层就只要找到合适的位置插入即可，一般不需要将数组完全遍历
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        int insertVal = 0;
        int insertIndex = 0;
        // 使用for 循环来吧代码简化
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;// 即将我们需要比较的前一位就是现在排序好的数组
            // 给insertVal 找到合适的插入位置
            // 1. insertIndex >= 0 ,如果小于0 了，说明已经吧全部数据都比较过了
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }
    }
}
